package 五月打卡;

/*
 * @author  YxinMiracle
 * @date  2022-05-04 8:50
 * @Gitee: https://gitee.com/yxinmiracle
 */

public class 找出游戏的获胜者 {

    public int findTheWinner(int n, int k) {
        boolean[] validate = new boolean[n + 1]; // 表示有没有被删除
        int[] people = new int[n + 1]; // 浪费掉第一个位置
        for (int i = 1; i <= n; i++) {
            people[i] = i;
            validate[i] = false;
        }
        int total = n;
        int index = 1; // 开始的下标
        while (total != 1) {
            for (int i = 0; i < k; i++) { // 走k次
                if (validate[calIndex(index,n)] == false) { // 有没有被删除
                    if (i == k-1) {  // 代表走到了要删除的地方
                        validate[calIndex(index,n)] = true;
                        total--;
                    }
                } else { // 被删除了，就回退,并且往后一步走
                    i --;
                }
                index++;
            }
        }
        for (int i = 1; i <= n ; i++) {
            if (validate[i] == false) return i;
        }
        return 0;
    }


    // 计算下标
    public int calIndex(int nowIndex, int n) {
        if (nowIndex % n == 0){
            return n;
        }
        return (nowIndex % n);
    }

    public static void main(String[] args) {
        System.out.println(new 找出游戏的获胜者().findTheWinner(6 , 5));
    }

}
